package puf.m2.automaton;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import automata.State;
import automata.Transition;

public class AbstractFiniteAutomaton implements Automaton {

    /** The collection of states */
    private Set<State> states;
    /** The collection of letters which form an alphabet */
    private Set<Letter> alphabet;
    /** The collection of transitions */
    private Set<Transition> transitions;

    /** The collection of final states in this automaton. */
    protected Set<State> finalStates;
    /** The initial state. */
    protected State initialState = null;

    // internal attribute
    /**
     * A mapping from states to an array holding transitions from a state. This
     * is a sort of cashing.
     */
    private HashMap<State, Transition[]> transitionArrayFromStateMap = new HashMap();
    /**
     * A mapping from states to a list holding transitions from those states.
     */
    private HashMap<State, List<Transition>> transitionFromStateMap = new HashMap();
    /**
     * A mapping from state to a list holding transitions to those states.
     */
    private HashMap<State, List<Transition>> transitionToStateMap = new HashMap();
    /**
     * A mapping from states to an array holding transitions from a state. This
     * is a sort of cashing.
     */
    private HashMap<State, Transition[]> transitionArrayToStateMap = new HashMap();

    /** The cached array of transitions. */
    private Transition[] cachedTransitions = null;

    /** The cached array of final states. */
    private State[] cachedFinalStates = null;
    /** The cached array of states. */
    private State[] cachedStates = null;

    /** Construct a new automaton with no states and no transitions */
    public AbstractFiniteAutomaton() {
        states = new HashSet<State>();
        transitions = new HashSet<Transition>();
        finalStates = new HashSet<State>();
        initialState = null;
    }

    public Automaton clone() {
        //TODO
        return null;
    }

    /**
     * Creates a state, inserts it in this automaton, and returns that state.
     * The ID for the state is set appropriately.
     */
    public State createState() {
        int i = 0;
        while (getStateWithID(i) != null)
            i++;
        State state = new State(i, this);
        addState(state);
        return state;
    }

    /**
     * Creates a state, inserts it in this automaton, and returns that state.
     * @param id
     *      the id to be associated with the new state
     */
    public final State createStateWithId(int id) {
        State state = new State(id, this);
        addState(state);
        return state;
    }

    /**
     * Returns the <CODE>State</CODE> in this automaton with this ID.
     * @param id
     *            the ID to look for
     * @return the instance of <CODE>State</CODE> in this automaton with this
     *         ID, or <CODE>null</CODE> if no such state exists
     */
    public State getStateWithID(int id) {
        Iterator<State> it = states.iterator();
        while (it.hasNext()) {
            State state = (State) it.next();
            if (state.id() == id)
                return state;
        }
        return null;
    }

    @Override
    public State[] getFinalStates() {
        if (cachedFinalStates == null)
            cachedFinalStates = (State[]) finalStates.toArray(new State[0]);
        return cachedFinalStates;
    }

    /**
     * Returns the start state for this automaton.
     * @return the start state for this automaton
     */
    public State getInitialState() {
        return this.initialState;
    }

    /**
     * Returns an array that contains every state in this automaton. The array
     * is guaranteed to be in order of ascending state IDs.
     * @return an array containing all the states in this automaton
     */
    public State[] getStates() {
        if (cachedStates == null) {
            cachedStates = (State[]) states.toArray(new State[0]);
            Arrays.sort(cachedStates, new Comparator<State>() {
                public int compare(State o1, State o2) {
                    return ((State) o1).id() - ((State) o2).id();
                }

                public boolean equals(Object o) {
                    return this == o;
                }
            });
        }
        return cachedStates;
    }

    @Override
    public Transition[] getTransitions() {
        if (cachedTransitions == null)
            cachedTransitions = (Transition[]) transitions
                    .toArray(new Transition[0]);
        return cachedTransitions;
    }

    @Override
    public void addTransition(Transition trans) {
        if (!Transition.class.isInstance(trans) || trans == null) {
            throw new IncompatibleTransitionException();
        }
        if (transitions.contains(trans))
            return;
        if(trans.target() == null || trans.source() == null) return;
        transitions.add(trans);
        if(transitionFromStateMap == null)
            transitionFromStateMap = new HashMap<State, List<Transition>>();
        List<Transition> list = (List<Transition>) transitionFromStateMap.get(trans.source());
        list.add(trans);
        if(transitionToStateMap == null)
            transitionToStateMap = new HashMap<State, List<Transition>>();
        list = (List<Transition>)transitionToStateMap.get(trans.target()) ;
        list.add(trans);
        transitionArrayFromStateMap.remove(trans.source());
        transitionArrayToStateMap.remove(trans.target());
        cachedTransitions = null;
    }

    @Override
    public void removeTransition(Transition trans) {
        transitions.remove(trans);
        List<Transition> l = (List<Transition>) transitionFromStateMap.get(trans.source());
        l.remove(trans);
        l = (List<Transition>) transitionToStateMap.get(trans.target());
        l.remove(trans);
        // Remove cached arrays.
        transitionArrayFromStateMap.remove(trans.source());
        transitionArrayToStateMap.remove(trans.target());
        cachedTransitions = null;
    }

    @Override
    public void addState(State state) {
        states.add(state);
        transitionFromStateMap.put(state, new LinkedList<Transition>());
        transitionToStateMap.put(state, new LinkedList<Transition>());
        cachedStates = null;
    }

    @Override
    public void removeState(State state) {
        Transition[] t;
        // from states
        t = getTransitionsFromState(state);
        for (int i = 0; i < t.length; i++)
            removeTransition(t[i]);
        // to states
        t = getTransitionsToState(state);
        for (int i = 0; i < t.length; i++)
            removeTransition(t[i]);
        states.remove(state);
        finalStates.remove(state);
        if (state == initialState)
            initialState = null;

        transitionFromStateMap.remove(state);
        transitionToStateMap.remove(state);

        transitionArrayFromStateMap.remove(state);
        transitionArrayToStateMap.remove(state);

        cachedStates = null;
    }

    /**
     * Retrieves all transitions that eminate from a state.
     *
     * @param from
     *            the <CODE>State</CODE> from which returned transitions
     *            should come from
     * @return an array of the <CODE>Transition</CODE> objects emanating from
     *         this state
     */
    public Transition[] getTransitionsFromState(State from) {
        Transition[] trans = (Transition[]) transitionArrayFromStateMap.get(from);
        if (trans == null) {
            List<Transition> list = (List<Transition>) transitionFromStateMap.get(from);
            trans = (Transition[]) list.toArray(new Transition[0]);
            transitionArrayFromStateMap.put(from, trans);
        }
        return trans;
    }

    /**
     * Retrieves all transitions that travel from a state.
     *
     * @param to
     *            the <CODE>State</CODE> to which all returned transitions
     *            should go to
     * @return an array of all <CODE>Transition</CODE> objects going to the
     *         State
     */
    public Transition[] getTransitionsToState(State to) {
        Transition[] trans = (Transition[]) transitionArrayToStateMap.get(to);
        if (trans == null) {
            List<Transition> list = (List<Transition>) transitionToStateMap.get(to);
            trans = (Transition[]) list.toArray(new Transition[0]);
            transitionArrayToStateMap.put(to, trans);
        }
        return trans;
    }

    /**
     * Retrieves all transitions going from one given state to another given
     * state.
     *
     * @param from
     *            the state all returned transitions should come from
     * @param to
     *            the state all returned transitions should go to
     * @return an array of all transitions coming from <CODE>from</CODE> and
     *         going to <CODE>to</CODE>
     */
    public Transition[] getTransitionsFromStateToState(State from, State to) {
        Transition[] t = getTransitionsFromState(from);
        ArrayList list = new ArrayList();
        for (int i = 0; i < t.length; i++)
            if (t[i].target() == to)
                list.add(t[i]);
        return (Transition[]) list.toArray(new Transition[0]);
    }

    /**
     * Sets the new initial state to <CODE>initialState</CODE> and returns
     * what used to be the initial state, or <CODE>null</CODE> if there was no
     * initial state. The state specified should already exist in the automata.
     *
     * @param initialState
     *            the new initial state
     * @return the old initial state, or <CODE>null</CODE> if there was no
     *         initial state
     */
    public State setInitialState(State state) {
        State oldInitialState = this.initialState;
        this.initialState = state;
        return oldInitialState;
    }

    public void removeFinalState(State state) {
        cachedFinalStates = null;
        finalStates.remove(state);
    }

    public void addFinalState(State state) {
        cachedFinalStates = null;
        finalStates.add(state);
    }

    public boolean isFinalState(State state) {
        return finalStates.contains(state);
    }

    public boolean isInitialState(State state) {
        return (state.equals(initialState));
    }

    /**
     * Reset all non-transient data structures.
     */
    @SuppressWarnings("rawtypes")
    protected void clear(){
        HashSet t;
        t = new HashSet<Transition>(transitions);
        for (Object o:t)
            removeTransition((Transition)o);
        transitions = new HashSet<Transition>();

        t = new HashSet<State>(states);
        for (Object o:t)
            removeState((State)o);
        states = new HashSet<State>();

        finalStates = new HashSet<State>();

        initialState = null;

        cachedStates = null;

        cachedTransitions = null;

        cachedFinalStates = null;

        transitionFromStateMap = new HashMap<State, List<Transition>>();
        transitionToStateMap = new HashMap<State, List<Transition>> ();

        transitionArrayFromStateMap = new HashMap<State, Transition[]>();

        transitionArrayToStateMap = new HashMap<State, Transition[]>();
    }
}
